package com.cg.leetcode;

import org.junit.Test;

/**
 * 707.设计链表
 *
 * @author cg
 * @program LeetCode->LeetCode_707
 * @create 2022-07-09 09:03
 **/
public class LeetCode_707 {

    @Test
    public void test707() {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);
        System.out.println(linkedList);
        linkedList.addAtTail(3);
        System.out.println(linkedList);
        linkedList.addAtIndex(1, 2);
        System.out.println(linkedList);
        System.out.println(linkedList.get(1));
        linkedList.deleteAtIndex(1);
        System.out.println(linkedList);
        System.out.println(linkedList.get(1));


        MyLinkedList2 linkedList2 = new MyLinkedList2();
        linkedList2.addAtHead(1);
        System.out.println(linkedList2);
        linkedList2.addAtTail(3);
        System.out.println(linkedList2);
        linkedList2.addAtIndex(1, 2);
        System.out.println(linkedList2);
        System.out.println(linkedList2.get(1));
        linkedList2.deleteAtIndex(1);
        System.out.println(linkedList2);
        System.out.println(linkedList2.get(1));
    }

    /**
     * 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
     * <p>
     * 在链表类中实现这些功能：
     * <p>
     * get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
     * addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
     * addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
     * addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
     * deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
     * <p>
     * 示例：
     * MyLinkedList linkedList = new MyLinkedList();
     * linkedList.addAtHead(1);
     * linkedList.addAtTail(3);
     * linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
     * linkedList.get(1);            //返回2
     * linkedList.deleteAtIndex(1);  //现在链表是1-> 3
     * linkedList.get(1);            //返回3
     * <p>
     * 提示：
     * 所有val值都在 [1, 1000] 之内。
     * 操作次数将在  [1, 1000] 之内。
     * 请不要使用内置的 LinkedList 库。
     */
    class MyLinkedList {

        int size;
        ListNode head;

        public MyLinkedList() {
            size = 0;
            head = new ListNode(-1);
        }

        public int get(int index) {
            if (index < 0 || index >= size) {
                return -1;
            }
            ListNode current = head.next;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            return current.val;
        }

        public void addAtHead(int val) {
            addAtIndex(0, val);
        }

        public void addAtTail(int val) {
            addAtIndex(size, val);
        }

        public void addAtIndex(int index, int val) {
            if (index > size) {
                return;
            }
            index = Math.max(index, 0);
            ListNode current = head, node = new ListNode(val);
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            node.next = current.next;
            current.next = node;
            size++;
        }

        public void deleteAtIndex(int index) {
            if (index >= 0 && index < size) {
                ListNode current = head;
                for (int i = 0; i < index; i++) {
                    current = current.next;
                }
                current.next = current.next.next;
                size--;
            }
        }

        @Override
        public String toString() {
            return "MyLinkedList{" +
                    "size=" + size +
                    ", head=" + head +
                    '}';
        }
    }

    class MyLinkedList2 {

        class LinkedNode {
            int val;
            LinkedNode per, next;

            public LinkedNode(int val) {
                this.val = val;
            }
        }

        int size;
        LinkedNode head, tail;

        public MyLinkedList2() {
            size = 0;
            head = new LinkedNode(-1);
            tail = new LinkedNode(-1);
            head.next = tail;
            tail.per = head;
        }

        public int get(int index) {
            if (index < 0 || index >= size) {
                return -1;
            }

            LinkedNode current;
            if (index < (size - 1) / 2) {
                current = head.next;
                for (int i = 0; i < index; i++) {
                    current = current.next;
                }
            } else {
                current = tail.per;
                for (int i = 0; i < size - 1 - index; i++) {
                    current = current.per;
                }
            }
            return current.val;
        }

        public void addAtHead(int val) {
            LinkedNode node = new LinkedNode(val);
            node.next = head.next;
            node.per = head;
            head.next.per = node;
            head.next = node;
            size++;
        }

        public void addAtTail(int val) {
            LinkedNode node = new LinkedNode(val);
            node.next = tail;
            node.per = tail.per;
            tail.per.next = node;
            tail.per = node;
            size++;
        }

        public void addAtIndex(int index, int val) {
            if (index > size) {
                return;
            }
            index = Math.max(index, 0);
            LinkedNode current = head, node = new LinkedNode(val);
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            node.next = current.next;
            node.per = current;
            current.next.per = node;
            current.next = node;
            size++;
        }

        public void deleteAtIndex(int index) {
            if (index >= 0 && index < size) {
                LinkedNode current = head;
                for (int i = 0; i < index; i++) {
                    current = current.next;
                }
                current.next.next.per = current;
                current.next = current.next.next;
                size--;
            }
        }

        @Override
        public String toString() {
            return "MyLinkedList2{" +
                    "size=" + size +
                    ", head=" + head +
                    '}';
        }
    }

}
